#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);

#define BUFFER_SIZE 10

typedef struct {
    . . .  // This struct defines what an "item" is
} item;

item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;

message next_produced;
while (true) {
    /* produce an item in next_produced */

    send(next_produced);
}

fd = shm_open(name, O_CREAT | O_RDWR, 0666);

mach_port_t port; // This is the name (an integer) for the port right
mach_port_allocate(
    mach_task_self(),      // A reference to the current task
    MACH_PORT_RIGHT_RECEIVE, // The right to create for this port
    &port);                // Where to store the port name

RemoteService service; // This is actually the stub object
...
boolean result = service.remoteMethod(3, 0.14); // Calls the remote service

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int sum; /* this data is shared by the thread(s) */
void *runner(void *param); /* threads call this function */

#include <windows.h>
#include <stdio.h>

DWORD Sum; /* data is shared by the thread(s) */

class Task implements Runnable {
    public void run() {
        System.out.println("I am a thread.");
    }
}

public interface Executor {
    void execute(Runnable command);
}

DWORD WINAPI PoolFunction(PVOID Param) {
    /* this function runs as a separate thread from the pool. */
}

ExecutorService pool = Executors.newCachedThreadPool();

ForkJoinPool pool = new ForkJoinPool();
int[] array = new int[SIZE]; // This array contains the integers to be summed
SumTask task = new SumTask(0, SIZE - 1, array); // The task to sum the whole array
int sum = pool.invoke(task); // Submit the task and get the final result

#include <omp.h>
#include <stdio.h>

int main(int argc, char *argv[])
{
    /* sequential code */ // This runs once, on the main thread.

    #pragma omp parallel
    {
        printf("I am a parallel region.\n");
    }

    /* sequential code */ // This also runs once, after the parallel region.
    return 0;
}

// 1. Get a reference to a system-wide concurrent queue.
//    We specify the .userInitiated Quality of Service class.
let queue = DispatchQueue.global(qos: .userInitiated)

// 2. Submit a task (closure) to the queue to be executed asynchronously.
//    The dispatch async() function returns immediately, without waiting for the task to finish.
dispatchAsync(queue) {
    print("I am a closure running on a concurrent queue.")
}

// Sequential for loop
for (int i = 0; i < n; i++) {
    apply(v[i]);
}

while (1) {
    /* do some work for awhile */
    ...

    /* check if there is a cancellation request */
    pthread_testcancel();
}

Thread worker;
. . .
// Set the interruption status of the thread
worker.interrupt();

static __thread int threadID;

while (true) {
    /* produce an item in next_produced */

    while (count == BUFFER_SIZE)
        ; /* do nothing - wait if buffer is full */

    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    count++;
}

while (true) {
    /* ENTRY SECTION */
    /* Request permission to enter */

    /* CRITICAL SECTION */
    /* Access and update shared data */

    /* EXIT SECTION */
    /* Signal departure from critical section */

    /* REMAINDER SECTION */
    /* Code that does not use shared data */
}

while (true) {
    // ENTRY SECTION
    flag[i] = true;          // Step 1: I want to enter.
    turn = j;                // Step 2: Defer to the other process.

    // Busy-Wait Loop (part of entry section)
    while (flag[j] && turn == j)
        ; // Do nothing and wait.

    // CRITICAL SECTION
    /* Access and update shared data */

    // EXIT SECTION
    flag[i] = false;         // Step 3: I'm no longer interested.

    // REMAINDER SECTION
    /* Other code not using shared data */
}

boolean flag = false;
int x = 0;

x = 100;
memory_barrier(); // Ensures x=100 is globally visible BEFORE flag=true
flag = true;

boolean test_and_set(boolean *target) {
    boolean rv = *target; // Step 1: Read the old value
    *target = true;       // Step 2: Always set it to true (atomically with the read)
    return rv;            // Step 3: Return the OLD value
}

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;                  // Step 1: Atomically read current value
    if (*value == expected)             // Step 2: Compare (still part of atomic op)
        *value = new_value;             // Step 3: Conditionally update
    return temp;                        // Return the ORIGINAL value read in Step 1
}

void increment(atomic_int *v) {
    int temp;
    do {
        temp = *v; // Read the current value of the atomic variable
        // Try to swap. If *v hasn't changed since we read it (== temp),
        // set it to temp+1. If it has changed, the swap fails, and we retry.
    } while (temp != compare_and_swap(v, temp, temp + 1));
}

while (true) {
    acquire_lock();   // ENTRY SECTION: Get the lock
    // CRITICAL SECTION
    release_lock();   // EXIT SECTION: Release the lock
    // REMAINDER SECTION
}

S1;              // Execute the first statement
signal(synch);   // Signal that S1 is done (increments synch to 1)

typedef struct {
    int value;
    struct process *list; // Pointer to the head of a waiting queue
} semaphore;

wait(mutex);   // ENTRY
// CRITICAL SECTION
signal(mutex); // EXIT

condition x, y;

wait(mutex);          // ENTRY: Acquire the monitor lock.

// ... body of the original function F ...

// EXIT: Before leaving, check if there are processes
//       that were signaled and are waiting on 'next'.
if (next_count > 0)
    signal(next);     // Let one of them proceed.
else
    signal(mutex);    // Otherwise, just free the monitor lock.

void acquire(int time) {
    if (busy)
        x.wait(time);  // 'time' is the priority number! Shorter time = higher priority.
    busy = true;
}

wait(S);  // Acquires S.
wait(Q);  // Waits to acquire Q.
// ... Critical section using both S and Q ...
signal(S);
signal(Q);

int n;                      // Total number of buffers in the pool
semaphore mutex = 1;        // Binary semaphore (acts like a mutex lock). Ensures mutual exclusion for accessing the buffer pool itself. Initialized to 1 (unlocked).
semaphore empty = n;        // Counting semaphore. Tracks the number of EMPTY buffers. Initially, all `n` buffers are empty.
semaphore full = 0;         // Counting semaphore. Tracks the number of FULL buffers. Initially, there are zero full buffers.

while (true) {
    wait(full);        // Step 1: Wait until there's at least one full buffer (blocks if full == 0).
    wait(mutex);       // Step 2: Acquire lock to access the buffer pool.
    ... // Critical Section: Remove an item from the buffer.
    signal(mutex);     // Step 3: Release the buffer pool lock.
    signal(empty);     // Step 4: Signal that an empty buffer slot has been created.
    ... // Consume the item (outside the critical section, so it doesn't block others).
}

semaphore rw_mutex = 1;  // Binary semaphore. Main lock for writers AND the first/last reader.
semaphore mutex = 1;     // Binary semaphore. Protects the shared integer 'read_count' from race conditions.
int read_count = 0;      // Integer counter. Tracks the number of currently active readers.

semaphore chopstick[5]; // Each semaphore is initialized to 1.

void test(int i) {
    if ( (state[(i + 4) % 5] != EATING) &&  // Left neighbor is NOT eating
         (state[i] == HUNGRY) &&            // I am HUNGRY
         (state[(i + 1) % 5] != EATING) ) { // Right neighbor is NOT eating
        state[i] = EATING;                 // Change my state to EATING
        self[i].signal();                  // Wake me up if I was waiting
    }
}

atomic_t counter; // Declare an atomic integer
int value;

#include <pthread.h>

pthread_mutex_t mutex; // Declare a mutex variable

/* Create and initialize the mutex lock with default attributes */
pthread_mutex_init(&mutex, NULL);

#include <semaphore.h>
sem_t *sem;

/* Create the semaphore and initialize it to 1 */
sem = sem_open("/SEM", O_CREAT, 0666, 1);

#include <semaphore.h>
sem_t sem; // Declare a semaphore variable (usually in shared memory or global data)

/* Create the semaphore and initialize it to 1 */
sem_init(&sem, 0, 1);

pthread_mutex_t mutex;
pthread_cond_t cond_var;

/* Initialize the mutex with default attributes */
pthread_mutex_init(&mutex, NULL);

/* Initialize the condition variable with default attributes */
pthread_cond_init(&cond_var, NULL);

public class BoundedBuffer<E> {
    private static final int BUFFER_SIZE = 5;
    private int count, in, out;
    private E[] buffer;

    public BoundedBuffer() {
        count = 0; in = 0; out = 0;
        buffer = (E[]) new Object[BUFFER_SIZE];
    }

    /* Producers call this method */
    public synchronized void insert(E item) {
        // Implementation shown later (Figure 7.11)
    }

    /* Consumers call this method */
    public synchronized E remove() {
        // Implementation shown later (Figure 7.11)
    }
}

/* Producers call this method */
public synchronized void insert(E item) {
    while (count == BUFFER_SIZE) { // MUST USE WHILE LOOP
        try {
            wait();
        }
        catch (InterruptedException ie) { }
    }
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    count++;
    notify(); // Notify a waiting consumer
}

/* Consumers call this method */
public synchronized E remove() {
    E item;
    while (count == 0) { // MUST USE WHILE LOOP
        try {
            wait();
        }
        catch (InterruptedException ie) { }
    }
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    count--;
    notify(); // Notify a waiting producer
    return item;
}

public void someMethod() {
    /* non-critical section */
    // Can run concurrently with other threads

    synchronized(this) { // Acquire lock on 'this' object
        /* critical section */
        // Only one thread at a time can execute here
    } // Lock is automatically released here

    /* remainder section */
    // Can run concurrently again
}

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

Lock key = new ReentrantLock(); // Create a non-fair lock

key.lock();                      // Acquire the lock (blocks if unavailable)
try {
    /* CRITICAL SECTION */
} finally {
    key.unlock();                // Release lock in finally block
}

Lock key = new ReentrantLock();
Condition condVar = key.newCondition(); // Creates condition variable bound to 'key'

void update() {
    acquire();           // Programmer manages lock acquisition
    /* modify shared data */
    release();           // Programmer manages lock release
}

int counter = 0; // Shared variable

void update(int value) {
    counter += value; // NOT thread-safe! Read-modify-write race.
}

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

lock1 = get_lock(from);
lock2 = get_lock(to);
if (F(lock1) > F(lock2)) { swap(lock1, lock2); } // Ensure lock1 has lower order
acquire(lock1);
acquire(lock2);

for (j = 0; j < 128; j++)
    for (i = 0; i < 128; i++)
        data[i][j] = 0;  // BAD: Accesses column j across all rows

Level	Example	Volatile?	Typical Use
Primary Storage	Registers (inside CPU)	Volatile	Holding the data the CPU is working on right now.
	Cache (L1, L2, L3)	Volatile	A buffer between the super-fast CPU and slower RAM.
	Main Memory (RAM)	Volatile	Holding programs and data currently in use.
Secondary Storage	NVM Devices (e.g., SSDs, Flash)	Nonvolatile	Permanent storage for programs and data; faster than HDDs.
	HDDs (Hard Drives)	Nonvolatile	Permanent storage for programs and data; high capacity, low cost.
Tertiary Storage	Magnetic Tapes, Optical Discs	Nonvolatile	Archival and backup; very slow, very high capacity.

Program	Process
Passive entity (a file on disk)	Active entity (an executing instance)
Static	Dynamic - its state changes as it runs
Exists once	Can have multiple instances (e.g., three separate processes for three separate browser windows)

Type	Name	Typical Range	Example
PAN	Personal-Area Network	Several feet	Connecting a wireless headset to a phone via Bluetooth
LAN	Local-Area Network	Room, Building, Campus	A network connecting all computers in a university department using Ethernet or Wi-Fi
MAN	Metropolitan-Area Network	A city	A network connecting libraries across a city
WAN	Wide-Area Network	Country, Global	The internet, or a private network connecting a company's offices worldwide

Category	Windows Example	UNIX Example
Process Control	`CreateProcess()`, `ExitProcess()`, `WaitForSingleObject()`	`fork()`, `exit()`, `wait()`
File Management	`CreateFile()`, `ReadFile()`, `WriteFile()`, `CloseHandle()`	`open()`, `read()`, `write()`, `close()`
Device Management	`SetConsoleMode()`, `ReadConsole()`, `WriteConsole()`	`ioctl()`, `read()`, `write()`
Information Maintenance	`GetCurrentProcessID()`, `SetTimer()`, `Sleep()`	`getpid()`, `alarm()`, `sleep()`
Communications	`CreatePipe()`, `CreateFileMapping()`, `MapViewOfFile()`	`pipe()`, `shm_open()`, `mmap()`
Protection	`SetFileSecurity()`, `InitializeSecurityDescriptor()`	`chmod()`, `umask()`, `chown()`

Feature	UNIX/Linux (`fork()` and `exec()`)	Windows (`CreateProcess()`)
Core Action	Creates a duplicate copy of the parent.	Creates a new process and loads a specified program into it.
Address Space	Child inherits a copy of the parent's address space.	Child starts with the address space of a new program.
System Calls	Two steps: `fork()` (create copy) then `exec()` (load program).	One step: `CreateProcess()` does both at once.
Parameters	`fork()` takes no parameters.	`CreateProcess()` requires at least ten parameters.

Feature	Ordinary Pipes (UNIX & Windows)	Named Pipes (UNIX FIFOs)	Named Pipes (Windows)
Persistence	Temporary (lasts only while processes run)	Persistent (exists until deleted)	Persistent (exists until deleted)
Process Relationship	Required (Parent-Child)	Not Required	Not Required
Direction	Unidirectional	Half-Duplex (typically)	Full-Duplex
Network Use	No (same machine only)	No (same machine only)	Yes (same or different machines)
Data Type	Byte-oriented	Byte-oriented	Byte- or Message-oriented

Mode	State	Type
Off	`Disabled`	--
Deferred	`Enabled`	`Deferred`
Asynchronous	`Enabled`	`Asynchronous`

Time	Process	Instruction Executed	Value (after instruction)
T0	Producer	`register1 = count`	`register1 = 5`
T1	Producer	`register1 = register1 + 1`	`register1 = 6`
T2	Consumer	`register2 = count`	`register2 = 5` (Stale read!)
T3	Consumer	`register2 = register2 - 1`	`register2 = 4`
T4	Producer	`count = register1`	`count = 6`
T5	Consumer	`count = register2`	`count = 4` (Final incorrect state)

Feature	Original Monitor (`synchronized` + `wait/notify`)	`ReentrantLock` + `Condition`
Condition Variables	One unnamed condition per object	Multiple named conditions
Lock Fairness	Not guaranteed	Can specify fair locking
Try Lock	No	`tryLock()` available
Interruptible Wait	Yes (via `InterruptedException`)	Yes
Nested Locking	Automatic reentrancy	Automatic reentrancy

Thread	Allocation (A,B,C)	Max (A,B,C)	Need (A,B,C) = Max - Allocation
T₀	(0, 1, 0)	(7, 5, 3)	(7, 4, 3)
T₁	(2, 0, 0)	(3, 2, 2)	(1, 2, 2)
T₂	(3, 0, 2)	(9, 0, 2)	(6, 0, 0)
T₃	(2, 1, 1)	(2, 2, 2)	(0, 1, 1)
T₄	(0, 0, 2)	(4, 3, 3)	(4, 3, 1)

Thread	Allocation	Need
T₀	(0,1,0)	(7,4,3)
T₁	(3,0,2)	(0,2,0)
T₂	(3,0,2)	(6,0,0)
T₃	(2,1,1)	(0,1,1)
T₄	(0,0,2)	(4,3,1)

Translation Granule	Page Size(s)	Region Size(s)
4 KB	4 KB	2 MB, 1 GB
16 KB	16 KB	32 MB
64 KB	64 KB	512 MB

Step	Ref	Frame Contents (Queue: Head -> Tail)	Fault?	Notes
1	7	[7]	F	Load 7. Queue: 7
2	0	[7, 0]	F	Load 0. Queue: 7, 0
3	1	[7, 0, 1]	F	Load 1. Queue: 7, 0, 1
4	2	[2, 0, 1]	F	Replace oldest (7) with 2. Queue: 0, 1, 2
5	0	[2, 0, 1]	-	0 is already in memory.
6	3	[2, 3, 1]	F	Replace oldest (0) with 3. Queue: 1, 2, 3
7	0	[2, 3, 0]	F	Replace oldest (1) with 0. Queue: 2, 3, 0
8	4	[4, 3, 0]	F	Replace oldest (2) with 4. Queue: 3, 0, 4
...	...	...	...	... (Continues as per figure)

Step	Ref	Frame Contents (LRU Order: Most Recent -> Least Recent)	Fault?	Reasoning for Replacement
1	7	[7]	F	Load.
2	0	[0, 7]	F	Load 0. Now 0 is most recent, 7 is least recent.
3	1	[1, 0, 7]	F	Load 1. Order: 1 (newest), 0, 7 (oldest).
4	2	[2, 1, 0]	F	Need a frame. LRU page is 7 (last used at step 1). Evict 7, load 2. New order: 2, 1, 0.
5	0	[0, 2, 1]	-	Hit on 0. Reorder: Access 0 moves it to front. New order: 0 (newest), 2, 1 (oldest).
6	3	[3, 0, 2]	F	Need a frame. LRU page is 1. Evict 1, load 3. New order: 3, 0, 2.
7	0	[0, 3, 2]	-	Hit on 0. Reorder: 0 moves to front. Order: 0, 3, 2.
8	4	[4, 0, 3]	F	Need a frame. LRU page is 2. Evict 2, load 4. New order: 4, 0, 3.
9	2	[2, 4, 0]	F	Need a frame. LRU page is 3. Evict 3, load 2. New order: 2, 4, 0.
...	...	...	...	... (Continue as per Figure 10.15)

Class	`(R, M)`	Meaning	Priority to Replace
1	`(0, 0)`	Not recently used, Not modified (Clean and cold). Best victim.	Highest (Best)
2	`(0, 1)`	Not recently used, But modified (Dirty but cold). Good victim, but requires a write-back (page-out).	Second Best
3	`(1, 0)`	Recently used, Clean (Hot but clean). Likely to be used again soon.	Third
4	`(1, 1)`	Recently used, Modified (Hot and dirty). Very likely to be used again and requires write-back.	Lowest (Worst)

Process	Burst Time (ms)
P1	24
P2	3
P3	3

Process	Burst Time (ms)
P1	6
P2	8
P3	7
P4	3

Process	Arrival Time	Burst Time (ms)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

Process	Burst Time (ms)
P1	24
P2	3
P3	3

Chapter 1: Introduction¶

1.1 What Operating Systems Do¶

The Four Components of a Computer System¶

The Operating System as a Government¶

1.1.1 User View¶

1.1.2 System View¶

1.1.3 Defining Operating Systems¶

The Challenge of a Single Definition¶

What's Included in an Operating System?¶

The Modern Complexity: The Case of Mobile OSes¶

Summary Definition for This Book¶

Why Study Operating Systems?¶

1.2 Computer-System Organization¶

The Basic Computer System Layout¶

1.2.1 Interrupts¶

A Typical I/O Operation with Interrupts¶

1.2.1.1 Interrupts: A Detailed Overview¶

The Basic Interrupt Mechanism¶

The Need for Speed: The Interrupt Vector¶

Preserving State: The Importance of Saving and Restoring¶

1.2.1.2 Interrupt Implementation¶

The Step-by-Step Interrupt Mechanism¶

Advanced Interrupt-Handling Features¶

Interrupt Lines: Maskable vs. Nonmaskable¶

Interrupt Chaining: Handling Many Devices¶

Interrupt Priority Levels¶

Summary¶

1.2.2 Storage Structure¶

The Central Role of Memory¶

Nonvolatile Memory: The Bootstrap and Firmware¶

Storage Definitions and Notation¶

How the CPU Interacts with Memory¶

The Need for Secondary Storage¶

The Memory Hierarchy¶

Operating System Terminology for Storage¶

1.2.3 I/O Structure¶

The Importance of I/O Management¶

The Problem with Simple Interrupt-Driven I/O¶

The Solution: Direct Memory Access (DMA)¶

System Architecture: Buses vs. Switches¶

Putting It All Together: How a Modern Computer System Works¶

1.3 Computer-System Architecture¶

Introduction: Categorizing Systems by Processors¶

1.3.1 Single-Processor Systems¶

The Traditional Single-Core CPU¶

The Role of Special-Purpose Processors¶

How the OS Manages Special-Purpose Processors¶

The Key Definition of a Single-Processor System¶

1.3.2 Multiprocessor Systems¶

Introduction: The Dominance of Multiprocessing¶

Symmetric Multiprocessing (SMP)¶

The Evolution: Multicore Systems¶

Definitions of Computer System Components¶

Scaling Beyond the Bus: Non-Uniform Memory Access (NUMA)¶

Blade Servers¶

1.3.3 Clustered Systems¶

What is a Clustered System?¶

Primary Goal: High-Availability¶

Types of Clustering: Asymmetric vs. Symmetric¶

Secondary Goal: High-Performance Computing¶

Parallel Clusters and Shared Data¶

The Role of Storage-Area Networks (SANs)¶

PC Motherboard (Sidebar)¶

1.4 Operating-System Operations¶

Introduction: The OS as an Execution Environment¶

Booting the System: The Bootstrap Program¶

System Startup: The Kernel and Daemons¶

Event-Driven Execution: The Role of Interrupts¶

Hadoop (Sidebar)¶

1.4.1 Multiprogramming and Multitasking¶

The Need for Running Multiple Programs¶

How Multiprogramming Works¶

From Multiprogramming to Multitasking¶

The OS Mechanisms Required for Multiprogramming/Multitasking¶

1.4.2 Dual-Mode and Multimode Operation¶

The Need for Protection¶

Dual-Mode Operation¶

How the Transition Works¶

Privileged Instructions: The Enforcer of Protection¶

Beyond Two Modes: Multimode Operation¶